#include "Multitree.h"
#include "Tuplets.h"



	//This function should be probably separated to some more functions.
namespace SymCe{
	Multitree * add_and_multiply(OperatorType oper, ListOfChilds * childs);
	Multitree * function_values(Multitree * tree);

	Multitree * canonicalize_tree(Multitree * tree){
		Multitree * one = copy_tree(tree);
		Multitree * two = reduce_tree(one);
		Multitree * tmp = NULL;
		rehang_tree(two);
		sort_tree(two);
		//Reduce tree, until nothing more can be done 
		//(when calling rehang, some nodes can come up that could be reduced more)
		while (treecmp(one, two) != 0){
			delete_tree(one);
			one = reduce_tree(two);
			rehang_tree(one);
			sort_tree(one);
			tmp = two;
			two = one;
			one = tmp;
		}
		//two and one are now identical.
		delete_tree(one);
		one = NULL;
		tmp=NULL;
		return two;
	}



	
	Multitree * reduce_tree(Multitree * tree){
		//This function reduces tree - it prunes parts like 0*<something> and similar
		Multitree * to_return = NULL;
		Multitree * argument = NULL;
		Multitree * tmp = NULL;

		
		switch(tree->symbol.type){
			case CONSTANT:
			case VARIABLE:
			case NUMBER:
				//We do nothing
				return copy_tree(tree);
				break;
			case FUNCTION:
				//We edit subtree and then put it as argument of the function (we make copy of this node)
				//We can of course find the value of the functions.
				argument = reduce_tree(tree->childs->subtree);
				to_return = new Multitree;
				to_return->symbol = tree->symbol;
				to_return->childs = new ListOfChilds;
				to_return->childs->inverted = false; //Probably not needed.
				to_return->childs->next = NULL;
				to_return->childs->subtree = argument;
				if (argument->symbol.type == NUMBER){
					tmp = function_values(to_return);
					delete_tree(to_return);
					to_return = tmp;
				}

				return to_return;
				break;
			case OPERATOR:
				//Reduce childs first. And put them back in same order!
				//There is at least one child (in fact there are at least two)
				ListOfChilds * pass = tree->childs;
				ListOfChilds * childs = new ListOfChilds;
				childs->inverted = pass->inverted;
				childs->next = NULL;
				childs->subtree = reduce_tree(pass->subtree);
				ListOfChilds * added = childs;
				pass = pass->next;
				while (pass != NULL){
					added->next = new ListOfChilds;
					added = added->next;
					added->inverted = pass->inverted;
					added->next = NULL;
					added->subtree = reduce_tree(pass->subtree);
					pass = pass->next;
				}
				//Childs are reduced. What now?

				//if it is power, then do something special if it is 1^<something> or 0^<something> or <something>^0
				
				if (tree->symbol.oper == POWER){				
					if((childs->subtree->symbol.type == NUMBER)
						&& (childs->subtree->symbol.number == 1)){
							to_return = new Multitree;
							to_return->childs = NULL;
							to_return->symbol.type = NUMBER;
							to_return->symbol.number = 1;
							delete_childs(childs);
							return to_return;
					}

					//something to 0 is 1
					if((childs->next->subtree->symbol.type == NUMBER)
						&& (childs->next->subtree->symbol.number == 0)){
							to_return = new Multitree;
							to_return->childs = NULL;
							to_return->symbol.type = NUMBER;
							to_return->symbol.number = 1;
							delete_childs(childs);
							return to_return;
					}

					//0 to something is 0.
					if((childs->subtree->symbol.type == NUMBER)
						&& (childs->subtree->symbol.number == 0)){
							to_return = new Multitree;
							to_return->childs = NULL;
							to_return->symbol.type = NUMBER;
							to_return->symbol.number = 0;
							delete_childs(childs);
							return to_return;
					}

					//Something to 1 is that something
					if((tree->childs->next->subtree->symbol.type == NUMBER)
						&& (tree->childs->next->subtree->symbol.number == 1)){
							to_return = copy_tree(tree->childs->subtree);
							delete_childs(childs);
							return to_return;
					}

					//In other cases return power with reduced childs.

					to_return = new Multitree;
					to_return->symbol = tree->symbol;
					to_return->childs = childs;
					return to_return;
					break;
				}else{
					//Now we have plus or multiply. We pass list of childs there and return something
					to_return = add_and_multiply(tree->symbol.oper, childs);
					delete_childs(childs);
					return to_return;
				}
		}
		//assert(false);
		return NULL;
	}

	Multitree * add_and_multiply(OperatorType oper, ListOfChilds * childs){
		Number number;
		Multitree * to_return = NULL;
		ListOfChilds * pass = NULL;
		ListOfChilds * added = NULL;
		ListOfChilds * newchilds = NULL;
		ListOfChilds * oldchilds = NULL;
		//First we want to bring some childs up.
		//We create new tree, rehang it and then delete its top node (childs are enough).
		Multitree * tree = new Multitree;
		Multitree * tmp = NULL;
		tree->symbol.type = OPERATOR;
		tree->symbol.oper = oper;
		tree->childs = childs;
		//We created new tree, but put there old childs. We copy it to new one so that we get new childs.
		tmp = copy_tree(tree);
		delete tree;
		tree = tmp;
		tmp = NULL;
		//Now we rehang it
		rehang_tree(tree);
		sort_tree(tree);
		//point the pass to its childs
		pass = tree->childs;
		oldchilds = pass;
		//and delete topmost node.
		delete tree;
		tree = NULL;
		
		//Now we add numbers as we need.
		if(oper == MULTIPLY){
			number = 1;
			while(pass != NULL){
				if(pass->subtree->symbol.type == NUMBER){
					if(pass->inverted){
						number = number/pass->subtree->symbol.number;
					}else{
						number = number*pass->subtree->symbol.number;
					}
				}else{
					added = new ListOfChilds;
					added->subtree = copy_tree(pass->subtree);
					added->inverted = pass->inverted;
					added->next = newchilds;
					newchilds = added;
				}
				pass = pass->next;
			}
			added = NULL;
			//Maybe we should have done the same with constants, not only numbers. Nevermind.
			//If number is 0, then we return zero.
			if(number == 0){
				//We return 0 in the tree.
				delete_childs(newchilds);
				to_return = new Multitree;
				to_return->childs = NULL;
				to_return->symbol.type = NUMBER;
				to_return->symbol.number = 0;
				return to_return;
			}
			//if it is 1, we do not attach it.
			if(number != 1){
				added = new ListOfChilds;
				added->inverted = false;
				added->subtree = new Multitree;
				added->subtree->childs = NULL;
				added->subtree->symbol.type = NUMBER;
				added->subtree->symbol.number = number;
				added->next = newchilds;
				newchilds = added;
			}
		}else{
			//assert(oper == PLUS);
			//We basically copy the whole thing.
			number = 0;
			while(pass != NULL){
				if(pass->subtree->symbol.type == NUMBER){
					if(pass->inverted){
						number = number-pass->subtree->symbol.number;
					}else{
						number = number+pass->subtree->symbol.number;
					}
				}else{
					added = new ListOfChilds;
					added->subtree = copy_tree(pass->subtree);
					added->inverted = pass->inverted;
					added->next = newchilds;
					newchilds = added;
				}
				pass = pass->next;
			}
			added = NULL;
			//We just do not connect 0 to the beginning of this.
			if(number != 0){
				added = new ListOfChilds;
				added->inverted = false;
				added->subtree = new Multitree;
				added->subtree->childs = NULL;
				added->subtree->symbol.type = NUMBER;
				added->subtree->symbol.number = number;
				added->next = newchilds;
				newchilds = added;
			}
		}
		
		//Now we have the fully prepared childs in newchilds. We can delete oldchilds.
		delete_childs(oldchilds);
		//Do with newchilds, what has to be done.
		

		//This part adds or multiplies "compatible" subtrees.
		//For example 2*x+3*x = 5*x or cos(y)^6/cos(y)^2 = cos(y)^4
		//It creates new tree and does not do it inplace
				
		Tuplet * a = NULL;
		Tuplet * b = NULL;
		//We convert childs to tuplets, add tuplets, remove unnecessary tuplets and convert it back to list.
		a = childs_to_tuplets(oper, newchilds);
		//We can delete childs
		delete_childs(newchilds);
		newchilds = NULL;
		b = add_tuplets(a);
		delete_tuplets(a);
		a = NULL;
		a = remove_null_tuplets(b);
		delete_tuplets(b);
		b = NULL;
		newchilds = tuplets_to_childs(oper, a);
		delete_tuplets(a);
		a = NULL;
		
		//So we have new list of childs. Now, depending on the number of childs, we return tree.
		
		if (newchilds == NULL){
			//No childs
			to_return = new Multitree;
			to_return->childs = NULL;
			to_return->symbol.type = NUMBER;
			if(oper == MULTIPLY){
				to_return->symbol.number = 1;
			}else{
				to_return->symbol.number = 0;
			}
			return to_return;
		}

		if(newchilds->next == NULL){
			//One child.
			//If not inverted
			if(!(newchilds->inverted)){
				to_return = newchilds->subtree;
				delete newchilds;
				newchilds = NULL;
				return to_return;
			}else{
				//It is inverted, we return operator with two childs
				//Either -1*child or child^-1
				to_return = new Multitree;
				to_return->symbol.type = OPERATOR;
				
				to_return->childs = new ListOfChilds;
				to_return->childs->inverted = false;
				to_return->childs->next = new ListOfChilds;
				to_return->childs->next->next = NULL;
				to_return->childs->next->inverted = false;

				Multitree * minusone = new Multitree;
				minusone->childs = NULL;
				minusone->symbol.type = NUMBER;
				minusone->symbol.number = -1;
				
				if(oper == MULTIPLY){
					to_return->symbol.oper = POWER;
					to_return->childs->subtree = newchilds->subtree;
					to_return->childs->next->subtree = minusone;
				}else{
					to_return->symbol.oper = MULTIPLY;
					to_return->childs->subtree = minusone;
					to_return->childs->next->subtree = newchilds->subtree;
				}
				delete newchilds;
				return to_return;
			}
		}
		//There are more than one newchild
		to_return = new Multitree;
		to_return->symbol.type = OPERATOR;
		to_return->symbol.oper = oper;
		to_return->childs = newchilds;
		sort_tree(to_return);
		return to_return;
	}

	Multitree * function_values(Multitree * tree){
		//If the value of the function is known (basically if its argument is zero) then return that value.
		//otherwise do not change the tree.
		Multitree * to_return = NULL;

		if (tree->symbol.type != FUNCTION){
			return copy_tree(tree);
		}

		if (tree->childs->subtree->symbol.type != NUMBER){
			return copy_tree(tree);
		}


		switch(tree->symbol.func){
			case SIN:
			case TAN:
			case COS:
				if (tree->childs->subtree->symbol.number == 0){
					to_return = give_me_empty_tree();
					to_return->childs = NULL;
					to_return->symbol.type = NUMBER;
					to_return->symbol.number = 0;
					if (tree->symbol.func == COS){
						to_return->symbol.number = 1;
					}
					return to_return;
				}
				break;
			case LN:
				//for logarithm our number is one
				if (tree->childs->subtree->symbol.number == 1){
					to_return = give_me_empty_tree();
					to_return->childs = NULL;
					to_return->symbol.type = NUMBER;
					to_return->symbol.number = 0;
					return to_return;
				}
				break;
		}
		return copy_tree(tree);
	}





}

